package LC;

import java.util.*;

/**
 * https://leetcode.com/problems/word-ladder-ii/description/
 * Given two words (beginWord and endWord), and a dictionary's word list,
 * find all shortest transformation sequence(s) from beginWord to endWord, such that:
 * Only one letter can be changed at a time
 * Each transformed word must exist in the word list.
 * Note that beginWord is not a transformed word.
 * For example,
 * Given:
 * beginWord = "hit"
 * endWord = "cog"
 * wordList = ["hot","dot","dog","lot","log","cog"]
 * Return
 * [
 * ["hit","hot","dot","dog","cog"],
 * ["hit","hot","lot","log","cog"]
 * ]
 * Note:
 * Return an empty list if there is no such transformation sequence.
 * All words have the same length.
 * All words contain only lowercase alphabetic characters.
 * You may assume no duplicates in the word list.
 * You may assume beginWord and endWord are non-empty and are not the same.
 * UPDATE (2017/1/20):
 * The wordList parameter had been changed to a list of strings (instead of a set of strings).
 * Please reload the code definition to get the latest changes.
 */
public class LC_126_WordLadderII_HashSet_Queue {
    public static void main(String[] args) {
        List<List<String>> ladders = Solution.findLadders("hit", "cog", Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));
        System.out.println(ladders);
    }

    static class Solution {
        static List<List<String>> findLadders(String s, String t, List<String> w) {
            List<List<String>> ans = new LinkedList<>();
            if (s == null || t == null || w == null) {
                if (s == null && t == null) ans.add(Collections.singletonList(null));
                return ans;
            }
            if (s.equals(t)) {
                ans.add(Collections.singletonList(s));
                return ans;
            }
            int sn = s.length();
            if (w.size() == 0) return ans;
            HashSet<String> nv = new HashSet<>(w);
            HashSet<String> hv = new HashSet<>();
            if (!nv.contains(t)) return ans;
            nv.add(s);
            Queue<String> q = new LinkedList<>();
            q.add(s);
            HashMap<String, List<String>> m = new HashMap<>();
            char[] cs = new char[sn];
            boolean isFind = false;
            while (!q.isEmpty()) {
                int size = q.size();
                while (size-- > 0) {
                    String n = q.poll();
                    for (int i = 0; i < sn; i++) cs[i] = n.charAt(i);
                    for (int i = 0; i < sn; i++) {
                        for (char c = 'a'; c <= 'z'; c++) {
                            cs[i] = c;
                            String nn = new String(cs);
                            if (!nv.contains(nn)) continue;
                            if (hv.add(nn)) q.add(nn);
                            if (!m.containsKey(nn)) m.put(nn, new LinkedList<>());
                            m.get(nn).add(n);
                            if (nn.equals(t)) isFind = true;
                        }
                        cs[i] = n.charAt(i);
                    }
                }
                if (isFind) break;
                nv.removeAll(hv);
                hv.clear();
            }
            find(t, s, new LinkedList<>(), m, ans);
            return ans;
        }

        static void find(String t, String s, LinkedList<String> l, HashMap<String, List<String>> m, List<List<String>> ans) {
            l.addFirst(t);
            if (t.equals(s)) {
                ans.add(new LinkedList<>(l));
            } else {
                List<String> vs = m.get(t);
                if (vs != null) {
                    for (String v : vs) {
                        find(v, s, l, m, ans);
                    }
                }
            }
            l.removeFirst();
        }

    }
}
